package puzzle.projecteuler.p200;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Problem169B {
	
	private static Map<String, Long> cache = new HashMap<String, Long>();
	
	private static BigInteger TWO = new BigInteger("2");

	/**
	 * 递归 
	 * answer	: 178653872807
	 * time cost: 16 ms
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		
		BigInteger n = new BigInteger("10").pow(25);
		System.out.println(String.format("f(%d) = %d", n, f(n)));
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}

	private static long f(BigInteger n) {
		
		int m = n.toString(2).length();
		return g(n, m-1);
	}

	/**
	 * g(n,m)表示：将n表达成2的幂次之和，每个数出现次数不超过2次，且最大的幂次<=m，这种表达 方式的个数
	 * @param n
	 * @param m
	 * @return
	 */
	private static long g(BigInteger n, int m) {
		
		long r = -1L;
		if (n.compareTo(BigInteger.ZERO) < 0 || m < 0) {
			r = 0;
		} else if (n.compareTo(BigInteger.ZERO) == 0 || n.compareTo(BigInteger.ONE) == 0) {
			r = 1;
		} else {
			String key = n.toString() + "::" + m;
			if (cache.containsKey(key)) {
				return cache.get(key);
			} else {
				int t = n.toString(2).length();
				if (m > t-1) {
					r = g(n, t-1);
				} else if (m < t-2) {
					r = 0;
				} else {
					BigInteger a = n.subtract(TWO.pow(m));
					BigInteger b = n.subtract(TWO.pow(m+1));
					r = ((a.compareTo(BigInteger.ZERO) == 0)?1:g(a, m-1)) 
							+ ((b.compareTo(BigInteger.ZERO) == 0)?1:g(b, m-1)) 
							+ g(n, m-1);
				}
				cache.put(key, r);
			}
		}
		return r;
	}
}
